package com.xk._02算法篇._06greedy.leetcode;

import java.util.Arrays;
import java.util.Comparator;

/**
 * https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
 * @description: 452_用最少数量的箭引爆气球
 * @author: xu
 * @date: 2022/10/18 16:12
 */
public class Test02 {
    /*
     * 思路：
     *  将points里的每个区间按照右边界进行排序
     *  初始化pos为points里的最小右边界区间的右边界上
     *  遍历points，如果每个区间的左边界比pos大，pos右移，ans++
     */
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] > o2[1]) return 1;
                else if (o1[1] < o2[1]) return -1;
                return 0;
            }
        });
        int pos = points[0][1];
        int cnt = 1;
        for (int[] balloon : points) {
            if (balloon[0] > pos) {
                pos = balloon[1];
                cnt++;
            }
        }
        return cnt;
    }
}
